package com.wdc.dp;

public class E01Leetcode509 {

    public int fib(int n) {
        if (n < 2) return n;
        int[] fn = new int[n + 1];
        fn[0] = 0;
        fn[1] = 1;
        for (int i = 2; i < fn.length; i++) {
            fn[i] = fn[i - 1] + fn[i - 2];
        }
        return fn[fn.length - 1];
    }

    public static void main(String[] args) {
        E01Leetcode509 e01Leetcode509 = new E01Leetcode509();
        System.out.println(e01Leetcode509.fib(4));
    }

}
